1. Field of the Invention
The present invention pertains to the field of communication networks.
The present invention more particularly relates to TDMA (“Time Division Multiple Access”) multi-hop wireless networks.
2. Description of the Prior Art
In a multi-hop wireless network, a set of nodes equipped with wireless interfaces form a network infrastructure where data is forwarded through multiple wireless hops toward intended destinations. Initially used in military applications such as ad hoc networks, the multi-hop wireless communication paradigm is now applied to emerging commercial applications such as mesh networks, sensor networks, personal area networks and wireless wide area networks.
The present invention considers a multi-hop wireless network where transmissions are coordinated by a Time Division Multiple Access (TDMA) protocol. TDMA protocols are attractive because they can provide bandwidth and delay guarantees through conflict-free, periodic transmission schedules. They are currently being considered by emerging multi-hop wireless standards such as IEEE 802.16j Mobile Multi-Hop Relay [IEEE 802.16's Mobile Multihop Relay (MMR) Study Group, http://www.ieee802.org/16/sg/mmr/] that aim at enhancing the coverage of current single-hop IEEE 802.16 wireless systems and also address the well-known performance problems encountered by existing Carrier Sense Multiple Access (CSMA) protocols in multi-hop wireless environments.
In a TDMA protocol, all nodes are synchronized to a common time reference and transmissions occur periodically in a sequence of multi-slot frames. Each frame consists of a control sub-frame followed by a data sub-frame. Both sub-frames are of fixed duration and consist of several time slots. During each control sub-frame, various management functions are performed including synchronization and schedule computation/dissemination. During each slot of the data sub-frame, some nodes transmit conflict-free according to a network schedule that has been computed during a preceding control sub-frame. The schedule computation can be either decentralized (computed by the nodes) or centralized (computed and disseminated to the nodes by a single node that acts as network controller).
Central to the operation of any TDMA protocol is the synchronization mechanism that keeps the node clocks synchronized to a common time reference. This time reference enables nodes to transmit at each slot based on the network schedule. In case of centralized scheduling, it also enables the controller node to compute a network-wide conflict-free schedule that provides bandwidth and delay guarantees to all nodes in the network. The synchronization mechanism for any TDMA system should be highly acccurate, have bounded execution time (delay) and low overhead, be inexpensive and be widely applicable. Below, we describe these features in more detail and discuss their impact on TDMA protocol performance.
In practice, the node clocks can never be perfectly synchronized. A highly accurate synchronization mechanism should minimize all node clock drifts from the common time reference. It should also bound all clock drifts to enable the (offline) design of TDMA MAC protocol parameters such as slot guard time, which is a constant per-slot overhead during TDMA protocol operation. A highly-accurate synchronization mechanism should result in low per-slot guard time, therefore, small slot duration. Small slot duration yields small frame duration, which translates to low delay. It also enables control of transmissions at a fast time scale, which translates to efficient protocol operation.
The clock synchronization mechanism is executed during the control sub-frame and its execution time is a per-frame overhead. This overhead must be both bounded and minimized to enable optimal design of TDMA MAC protocol parameters such as the duration of the control sub-frame, which is fixed during the TDMA protocol operation.
The synchronization mechanism should not incur excessive additional cost to the wireless system.
Ideally, the synchronization mechanism should apply to different wireless environments (indoor/outdoor), different types of multi-hop wireless networks (mesh networks, personal area networks, sensor networks) and different types of devices (wireless routers operating within the infrastructure or clients operating at the wireless network edge).
No existing synchronization mechanism for multi-hop wireless networks can support all the above features.
Existing synchronization mechanisms can be broadly classified to out-of-band or in-band. Out-of-band synchronization mechanisms enforce a common time reference using additional hardware. For example, clock synchronization can be achieved at high accuracy if all wireless nodes are tuned to an external global clock through Global Positioning System (GPS) devices. This approach is not widely applicable because GPS devices are expensive and only work in outdoor environments with clear sky view.
In-band synchronization mechanisms attempt to synchronize the node clocks by sending beacon synchronization messages within the network. The simplest version of in-band synchronization mechanisms operate in today's wireless systems of star topology where a server node provides single-hop wireless access to fixed or mobile client nodes. Examples are GSM/TDMA cellular networks, satellite systems, IEEE 802.16 broadband wireless systems, IEEE 802.11 wireless LANs using the Point Coordination Function (PCF) or Bluetooth systems. In these single-hop wireless TDMA systems, time synchronization can be achieved by periodic broadcast transmissions of a signal or beacon packet from the server to all clients (see for instance U.S. Pat. No. 7,263,590 “System and method of timing and frequency control in TDM/TDMA networks”). This method cannot be applied to multi-hop wireless networks because a node providing network time reference cannot reach all other nodes with a single broadcast transmission.
A potential way to develop in-band synchronization mechanisms for multi-hop wireless networks is to adapt synchronization mechanisms for multi-hop wireline networks. The Network Time Protocol (NTP) is the most well-known clock synchronization mechanism currently used in the Internet [D. L. Mills. “Internet Time Synchronization: The Network Time Protocol.” In Zhonghua Yang and T. Anthony Marsland (Eds.), Global States and Time in Distributed Systems, IEEE Computer Society Press, 1994.]. NTP signaling is considered heavyweight for the wireless environment-existing wireless adaptations of NTP yield low accuracy and high overhead, even for the simple case of single-hop wireless networks.
Some in-band clock synchronization algorithms have been proposed for multi-hop wireless sensor networks, including the following:                J. Elson, L. Girod, and D. Estrin. “Fine-Grained Network Time Synchronization Using Reference Broadcasts.” In Proc. 5th Symposium on Operating Systems Design and Implementation (OSDI), 2002.        S. Ganeriwal, R. Kumar, and M. Srivastava. “Timing-sync Protocol for Sensor Networks.” In SENSYS, November 2003.        Q. Li and D. Rus. Global Clock Synchronization in Sensor Networks, 2004.        M. Maroti, B. Kusy, G. Simon, and A. Ledeczi. “The Flooding Time Synchronization Protocol.” In ACM Sen-Sys 2004, 2004.        M. Mock, R. Frings, E. Nett, and S. Trikaliotis. “Continuous Clock Synchronization in Wireless Real-Time Applications.” In Symposium on Reliability in Distributed Software, 2000.        K. Romer. “Time Synchronization in Ad Hoc Networks.” In ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 01), Long Beach, Calif., October 2001.        J. van Greunen, J. Rabaey, “Lightweight Time Synchronization for Sensor Networks”, In Proc. WSNA, September 2003, San Diego, Calif.        M. Xu, M. Zhao and S. Li, “Lightweight and energy efficient time synchronization for sensor network”, In Proc. International Conference on Wireless Communications, Networking and Mobile Computing, 2005.        
The above algorithms exploit the broadcast nature of the wireless medium to improve synchronization accuracy. However, they all use random access MAC protocols to disseminate the synchronization beacon packets in the network. Such protocols are not appropriate for TDMA systems because they introduce unpredictable delays and collisions that result in losses of synchronization beacon packets. Therefore such algorithms are not able to minimize or even bound the synchronization overhead. In addition, most of these algorithms have not been implemented and tested in real-world multi-hop wireless environments.
The IEEE 802.16 Relay Task group (802.16j standard) has specified an in-band synchronization mechanism for multi-hop 802.16 wireless systems that have a tree topology structure. This synchronization mechanism operates on top of the 802.16 TDMA protocol but is specific to a tree topology structure: synchronization preambles are disseminated from a central root node toward leaf nodes over the tree network structure. This mechanism cannot be applied to multi-hop wireless networks of general topology where parent-child roles are not known in advance. In addition, clock dissemination over a tree structure is subject to individual link failures: if at least one link fails to disseminate the preamble the synchronization algorithm fails to synchronize all nodes under a common time reference. Finally, the 802.16j draft standard only specifies general signaling and message exchanges but does not provide an algorithm to efficiently schedule the dissemination of synchronization signals so that the TDMA protocol conflict-free and bounded delay requirements are met.                Relay Task Group of IEEE 802.16, “Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Multihop Relay Specification”, IEEE P802.16j/D3, Feb. 29 2008.The ECMA High rate Ultra Wide Band PHY and MAC standard defines an in-band distributed clock synchronization mechanism that operates on top of a TDMA MAC protocol. In this mechanism, during each TDMA frame each node periodically broadcasts its clock to its one-hop neighbors and synchronizes its clock to the received clock value of its slowest one-hop neighbor. This “follow the slowest clock” method can synchronize nodes in a single-hop network where all nodes can hear each other. However, in a multi-hop wireless network, this algorithm would require an unbounded number of TDMA frames to propagate the slowest clock and create a common time reference for the entire network.As a consequence, the algorithm disclosed in the ECMA standard does not provide a solution for applications where a global network time reference is needed in minimum time and bounded delay.        “Standard ECMA 368, High Rate Ultra Wideband PHY and MAC standard.”, 2nd edition, December 2007.        
Among the publications of the prior art, the PCT patent application No. WO 2006/056174 (Fraunhofer—Germany) discloses a synchronization and data transmission method. The synchronization method disclosed in that prior Fraunhofer PCT patent application does not satisfy the TDMA protocol requirements of bounded delay and low overhead, and does not apply to a multi-hop wireless environment.